import math

"""
二分查找：
常见的二分查找，主要有两类用途：
1. 在一个有序数列里 查找一个具体数值的下标
2. 一个有序数列分成两个部分 [a， a， a， b， b， b， b]
通过二分查找来找到b部分的最小下标 或者 a部分的最大下标

二分查找在实现的时候有几个关键点：
a.while循环的终止条件
在1条件下是<= 因为对于两个边界重合的情况还要进行判断
在2条件下是< 因为两个边界的重合代表找到部分的边界了

b.关于mid的计算方式

c.关于查找范围的重新界定
"""

# 1. 在一个有序数列里 查找一个具体数值的下标
def bin_search(data_list, val):    
    low = 0                         # 最小数下标    
    high = len(data_list) - 1       # 最大数下标    
    while low <= high:
        """
        查找一个具体的数值 那么边界重合也是要判断的部分
        """        
        # mid = (low + high) // 2     # 中间数下标     
        mid = int( math.ceil( (low+high)/2 ) )  
        # mid = int( math.floor( (low+high)/2 ) ) 
        """
        情况1下 mid的计算 无论是ceil 还是 floor都是可以的
        """
        if data_list[mid] == val:   # 如果中间数下标等于val, 返回            
            return mid        
        elif data_list[mid] > val:  # 如果val在中间数左边, 移动high下标            
            high = mid - 1        
        else:                       # 如果val在中间数右边, 移动low下标            
            low = mid + 1
        """
        情况1下 因为mid已经判断过了 所以重新界定的边界不再包含mid
        mid大于寻找值 [low, mid-1]
        mid小于寻找值 [mid+1, high]
        """    
    return # val不存在, 返回None
ret = bin_search(list(range(1, 10)), 1)
# print(ret)

"""
2. 一个有序数列分成两个部分 [a， a， a， b， b， b， b]
通过二分查找来找到b部分的最小下标 或者 a部分的最大下标
"""
a = 0
b = 1
L = [a, a, a, a, b, b, b, b, b, b, b, b]
L2 = [b, b, b, b, b, b, b, b]

# 2.1 通过二分查找来找到b部分的最小下标

def bin_search_maxMin(data_list):
    low, high = 0, len(L)-1
    while low < high:
        """
        low high重合 说明找到边界了
        """

        mid = int( math.floor((low+high)/2) )
        # mid = int( math.ceil((low+high)/2) ) # 无限循环
        """
        b作为大的一边 需要向小的部分寻找 所以mid是取floor
        如果取ceil 会无限循环

        b的边界在左边 mid向左边尝试
        mid是b 那就high变成b 靠近边界
        mid是a mid+1 将a抬升 由a到a 或者a到b（边界）
        mid逐步向右直到high到达边界
        因为 情况可能是 [a， b(边界，low)， b(high)] high要靠mid右进 所以mid得取floor
        """
        if data_list[mid] == b:
            high = mid # high 是右的一方 依靠mid逐步向左走 但仍留在右部
        else:
            low = mid + 1 # 
    return low

print(bin_search_maxMin(L))

# 2.2 通过二分查找来找到最小部分的最大下标

def bin_search_minMax(data_list):
    low, high = 0, len(L)-1
    while low < high:
        """
        low high重合 说明找到边界了
        """

        # mid = int( math.floor((low+high)/2) ) # 无限循环
        mid = int( math.ceil((low+high)/2) ) 

        if data_list[mid] == a:
            low = mid # 
        else:
            high = mid - 1 # 
    return high

print(bin_search_minMax(L))